package SubjectTree.Two;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

import Utility.TreeNode;

public class IsSameTree {

/**
 * 难度：简单
 * 
 * 100. 相同的树
 * 	给定两个二叉树，编写一个函数来检验它们是否相同。
 * 	如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
 * 	
 * 示例 1:
 * 	输入:       1         1
 * 	          / \       / \
 * 	         2   3     2   3
 * 	        [1,2,3],   [1,2,3]
 * 	输出: true
 * 	
 * 示例 2:
 * 	输入:      1          1
 * 	          /           \
 * 	         2             2
 * 	        [1,2],     [1,null,2]
 * 	输出: false
 * 	
 * 示例 3:
 * 	输入:       1         1
 * 	          / \       / \
 * 	         2   1     1   2
 * 	        [1,2,1],   [1,1,2]
 * 	输出: false
 *
 * */
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		IsSameTree ist = new IsSameTree();
		System.out.println(ist.isSameTree_1(TreeNode.MkTree("[1,2,4]"), TreeNode.MkTree("[1,2,4]")));
	}
	//自己写(前序扫描)
	public boolean isSameTree(TreeNode p, TreeNode q) {
		if(p==null && q==null)return true;
		Deque<TreeNode> deque = new LinkedList<>();
		while(!deque.isEmpty() || p!=null || q!=null) {
			while(p!=null || q!=null) {
				if(p==null ^ q==null || p.val!=q.val)return false;
				deque.push(p);
				deque.push(q);
				p = p.left;
				q = q.left;
			}
			q = deque.pop();
			p = deque.pop();
			p = p.right;
			q = q.right;
		}
		return true; 
    }
	//自己写(递归)
	public boolean isSameTree_1(TreeNode p, TreeNode q) {
		if(p==null && q==null)return true;
		else if(p==null || q==null)return false;
		else if(p.val!=q.val)return false;
		else return isSameTree_1(p.left, q.left) && isSameTree_1(p.right, q.right);
    }
	
	//方法一：深度优先搜索
	public boolean isSameTree1(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        } else if (p == null || q == null) {
            return false;
        } else if (p.val != q.val) {
            return false;
        } else {
            return isSameTree1(p.left, q.left) && isSameTree1(p.right, q.right);
        }
    }
	//方法二：广度优先搜索
	public boolean isSameTree2(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        } else if (p == null || q == null) {
            return false;
        }
        Queue<TreeNode> queue1 = new LinkedList<TreeNode>();
        Queue<TreeNode> queue2 = new LinkedList<TreeNode>();
        queue1.offer(p);
        queue2.offer(q);
        while (!queue1.isEmpty() && !queue2.isEmpty()) {
            TreeNode node1 = queue1.poll();
            TreeNode node2 = queue2.poll();
            if (node1.val != node2.val) {
                return false;
            }
            TreeNode left1 = node1.left, right1 = node1.right, left2 = node2.left, right2 = node2.right;
            if (left1 == null ^ left2 == null) {
                return false;
            }
            if (right1 == null ^ right2 == null) {
                return false;
            }
            if (left1 != null) {
                queue1.offer(left1);
            }
            if (right1 != null) {
                queue1.offer(right1);
            }
            if (left2 != null) {
                queue2.offer(left2);
            }
            if (right2 != null) {
                queue2.offer(right2);
            }
        }
        return queue1.isEmpty() && queue2.isEmpty();
    }
}
